#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	
	vector<int> head(n + 1);
	vector<int> next((m << 1) + 1);
	vector<int> to((m << 1) + 1);
	vector<int> weight((m << 1) + 1);
        int edge = 1;
	for (int i = 0; i < m; i++) {
                int u, v, w;
                cin >> u >> v >> w;

                weight[edge] = w;
                next[edge] = head[u];
                to[edge] = v;
                head[u] = edge++;

                weight[edge] = w;
                next[edge] = head[v];
                to[edge] = u;
                head[v] = edge++;
	}

	vector<int> dis(n + 1, INT32_MAX);
	vector<int> vis(n + 1, 0);

	int ans = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.emplace(0, 1);
	while (!pq.empty()) {
		auto [w, u] = pq.top();
		pq.pop();
		if (vis[u]) {
			continue;
		}
		vis[u] = 1;

		if (u == n) {
			ans = w;
		}

		for (int e = head[u]; e; e = next[e]) {
			int v = to[e], c = weight[e];
			if (!vis[v] && w + c < dis[v]) {
				dis[v] = w + c;
				pq.emplace(w + c, v);
			}
		}
	}
	cout << ans << endl;
	return 0;
}